﻿#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;
//int getSum(int a, int b) {
//	int i = a & b;
//	int ret = a ^ b;
//	i <<= 1;
//	while (i != 0)
//	{
//		ret = (unsigned int)ret ^ (i);
//		i &= ret;
//		i <<= 1;
//	}
//	return ret;
//}
//int main()
//{
//	//	char k = -128;
//	//	for (int i = 7; i >= 0; i--)
//	//		printf("%d ", (k >> i) & 1);
//	//
//	//	char j = k<< 1;
//	//	printf("%d    %d", k, j);
//	cout << getSum(20, 30) << endl;
//	return 0;
//}
//class Solution {
//public:
//	string convert(string s, int numRows) {
//		if (numRows == 1)
//			return s;
//		if (s.size() <= numRows)
//			return s;
//		string ret;
//		int d = 2 * numRows - 2;
//		//处理第一行
//		for (int i = 0; i < s.size(); i += d)
//		{
//			ret.push_back(s[i]);
//		}
//		//处理第二行到倒数第二行
//		for (int j = 1; j < numRows - 1; j++)
//		{
//			ret.push_back(s[j]);
//			for (int i = d; i <= s.size(); i += d)
//			{
//				ret.push_back(s[i - j]);
//				if (i + j < s.size())
//					ret.push_back(s[i + j]);
//			}
//		}
//		//处理最后一行
//		for (int i = numRows - 1; i < s.size(); i += d)
//			ret.push_back(s[i]);
//		return ret;
//	}
//};
//int main()
//{
//	Solution s;
//	string str = "abcde";
//	s.convert(str, 4);
//	return 0;
//}
class Solution
{
	vector<int> ret;
	vector<int> index; // 记录 nums 中当前元素的原始下标
	int tmpNums[500010];
	int tmpIndex[500010];
public:
	vector<int> countSmaller(vector<int>& nums)
	{
		int n = nums.size();
		ret.resize(n);
		index.resize(n);
		// 初始化⼀下 index 数组
		for (int i = 0; i < n; i++)
			index[i] = i;
		mergeSort(nums, 0, n - 1);
		return ret;
	}

	void mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		// 1. 根据中间元素，划分区间
		int mid = (left + right) >> 1;
		// [left, mid] [mid + 1, right]
		// 2. 先处理左右两部分
		mergeSort(nums, left, mid);
		mergeSort(nums, mid + 1, right);
		// 3. 处理⼀左⼀右的情况
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) // 降序
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmpNums[i] = nums[cur2];
				tmpIndex[i++] = index[cur2++];
			}
			else
			{
				ret[index[cur1]] += right - cur2 + 1; // 重点
				tmpNums[i] = nums[cur1];
				tmpIndex[i++] = index[cur1++];
			}
		}
		// 4. 处理剩下的排序过程
		while (cur1 <= mid)
		{
			tmpNums[i] = nums[cur1];
			tmpIndex[i++] = index[cur1++];
		}
		while (cur2 <= right)
		{
			tmpNums[i] = nums[cur2];
			tmpIndex[i++] = index[cur2++];
		}
		for (int j = left; j <= right; j++)
		{
			nums[j] = tmpNums[j - left];
			index[j] = tmpIndex[j - left];
		}
	}
};

int main()
{
	return 0;
}